package pro.softzhang.algo.lc800;

import pro.softzhang.algo.common.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 *
 */
public class LC872_LeafSimilarTrees {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            List<Integer> leafs1 = new ArrayList<>(), leafs2 = new ArrayList<>();
            getLeafs(root1, leafs1);
            getLeafs(root2, leafs2);
            return Arrays.equals(leafs1.toArray(), leafs2.toArray());
        }

        private void getLeafs(TreeNode root, List<Integer> leafs) {
            if(root == null) {
                return;
            }
            if(root.left == null && root.right == null) {
                leafs.add(root.val);
                return;
            }

            getLeafs(root.left, leafs);
            getLeafs(root.right, leafs);
        }
    }

    static
    class Solution1 {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            List<Integer> leafs1 = getLeafs(root1), leafs2 = getLeafs(root2);
            return Arrays.equals(leafs1.toArray(), leafs2.toArray());
        }

        private List<Integer> getLeafs(TreeNode root) {
            List<Integer> leafs = new ArrayList<>();
            TreeNode p = root;
            Stack<TreeNode> stack = new Stack<>();
            while (p != null || !stack.isEmpty()) {
                if(p != null) {
                    stack.push(p);
                    p = p.left;
                } else {
                    TreeNode node = stack.pop();
                    if(node.left == null && node.right == null) {
                        leafs.add(node.val);
                    } else {
                        p = node.right;
                    }
                }
            }
            return leafs;
        }
    }
}
